Про префиксное дерево (Trie) написано немало, в том числе и на Хабре. Вот пример, как оно может выглядеть:

И даже реализаций в коде, в том числе на JavaScript, для него существует немало — от «каноничной» by John Resig и разных оптимизированных версий до серии модулей в NPM.

Зачем же нам понадобилось использовать его для сервиса по сбору и анализу планов PostgreSQL, да еще и «велосипедить» какую-то новую реализацию?..

«Склеенные» логи

Давайте посмотрим, на небольшой кусок лога сервера PostgreSQL:

2020-09-11 14:49:53.281 MSK [80927:619/4255507] [explain.tensor.ru] 10.76.182.154(59933) pgAdmin III - ???????????????????? ???????????????? LOG:  duration: 0.016 ms  plan: 	Query Text: explain analyze 	SELECT 		* 	FROM 		pg_class 	WHERE 		relname = 'мама 	мыла 	раму'; 	Index Scan using pg_class_relname_nsp_index on pg_class  (cost=0.29..2.54 rows=1 width=265) (actual time=0.014..0.014 rows=0 loops=1) 	  Index Cond: (relname = 'мама 	мыла